package lruCache;

import java.util.HashMap;

public class LRUCache {

    /**
     * key -> Node(key, val)
     */
    private HashMap<Integer, Node> map;

    /**
     * Node(key1, val1) <-> Node(key2, val2)...
     */
    private DoubleList cache;

    /**
     * max capacity
     */
    private int cap;


    public LRUCache(int capacity){
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    /**
     * LRUCache算法，获得特定key的值
     * @param key
     * @return
     */
    public int get(int key){
        if(!map.containsKey(key)){
            return -1;
        }
        //将该数据提升为最近使用
        makeRecently(key);
        return map.get(key).val;
    }

    /**
     * put cache algorithm
     * @param key
     * @param val
     */
    public void put(int key, int val){
        if(map.containsKey(key)){
            deleteKey(key);
            addRecently(key, val);
            return;
        }

        if(cap == cache.size()){
            removeLeastRecently();
        }

        addRecently(key, val);
    }


    /**
     * 将某个key提升为最近使用的
     * @param key
     */
    private void makeRecently(int key){
        Node n = map.get(key);
        cache.removeNode(n);
        cache.addNode(n);
    }

    /**
     * 添加最近使用的元素
     * @param key
     * @param val
     */
    private void addRecently(int key, int val){
        Node n = new Node(key, val);
        cache.addNode(n);
        map.put(key, n);
    }

    /**
     * 删除某一个key值
     * @param key
     */
    private void deleteKey(int key){
        Node n = map.get(key);
        cache.removeNode(n);
        map.remove(key);
    }

    /**
     * 删除最久未使用元素
     */
    private void removeLeastRecently(){
        Node n = cache.removeFirst();
        map.remove(n.key);
    }



}
